//
//  Problem700.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/5/23.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 700. 二叉搜索树中的搜索
 给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。

 例如，
 给定二叉搜索树:
         4
        / \
       2   7
      / \
     1   3
 和值: 2，你应该返回如下子树:
       2
      / \
     1   3
 在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。
 */
@objcMembers class Problem700: NSObject {
    func solution() {
        let root = TreeNode(4)
        root.left = TreeNode(2)
        root.left?.left = TreeNode(1)
        root.left?.right = TreeNode(3)
        
        root.right = TreeNode(7)
        
        print(printNodeTree(searchBST_BFS(root, 2)))
        print(printNodeTree(searchBST_BFS(root, 5)))
    }
    
    /*
     深度 递归
     */
    func searchBST(_ root: TreeNode?, _ val: Int) -> TreeNode? {
        if root == nil {
            return nil
        }
        if root!.val == val {
            return root
        } else if root!.val > val {
            return searchBST(root?.left, val)
        } else {
            return searchBST(root?.right, val)
        }
    }
    
    /*
     广度 迭代
     */
    func searchBST_BFS(_ root: TreeNode?, _ val: Int) -> TreeNode? {
        var node = root
        while node != nil {
            if node!.val == val {
                return node
            } else if node!.val > val {
                node = node?.left
            } else {
                node = node?.right
            }
        }
        return nil
    }
}
